package mht.leetCode.primary.string;

import java.util.Arrays;

public class Solution {

    /**
     * 【翻转字符串】
     *
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
     *
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     *
     * 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
     *
     * 示例 1：
     *
     * 输入：["h","e","l","l","o"]
     * 输出：["o","l","l","e","h"]
     * 示例 2：
     *
     * 输入：["H","a","n","n","a","h"]
     * 输出：["h","a","n","n","a","H"]
     *
     */
    public void reverseString(char[] s) {
        int l = s.length;

        for (int i = 0; i < l/2; i++) {
            char tmp = s[i];
            s[i] = s[l-i-1];
            s[l-i-1] = tmp;
        }
    }

    /**
     * 【整数翻转】
     *
     * 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
     *
     * 示例 1:
     *
     * 输入: 123
     * 输出: 321
     *  示例 2:
     *
     * 输入: -123
     * 输出: -321
     * 示例 3:
     *
     * 输入: 120
     * 输出: 21
     *
     */
    public int reverse(int x) {

        int res = 0;

        while (x != 0) {
            int tmp = x % 10;
            x /= 10;
            if (res > Integer.MAX_VALUE/10 || (res == Integer.MAX_VALUE / 10 && tmp > 7)) return 0;
            if (res < Integer.MIN_VALUE/10 || (res == Integer.MIN_VALUE / 10 && tmp < -8)) return 0;
            res = res * 10 + tmp;
        }
        return res;
    }

    /**
     * 【字符串中的第一个唯一字符】
     *
     * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
     *
     * 案例:
     *
     * s = "leetcode"
     * 返回 0.
     *
     * s = "loveleetcode",
     * 返回 2.
     *
     *
     * 注意事项：您可以假定该字符串只包含小写字母。
     */
    public int firstUniqChar(String s) {

        // 思路：因为只有小写字母，所以使用int[] 构建一个 26个字母对应的哈希表，查询value值是否为1，来进行判断出现的次数
        int[] count = new int[26];


        for(int i=0;i<s.length();i++)
        {
            count[s.charAt(i) -'a']++;
        }

        for(int i=0;i<s.length();i++)
        {
            if(count[s.charAt(i) -'a'] ==1)
                return i;
        }

        return -1;
    }

    /**
     * 【有效的字母异位词】
     *
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     *
     * 示例 1:
     *
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     * 示例 2:
     *
     * 输入: s = "rat", t = "car"
     * 输出: false
     * 说明:
     * 你可以假设字符串只包含小写字母。
     *
     * 进阶:
     * 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
     */
    public boolean isAnagram(String s, String t) {

        // 题目分析：
        // 根据题目的意思，字母异位词是指由相同的字母按照不同的顺序组成的单词，
        // 根据此含义，那么这两个单词的长度也一定相等，所以我们就可以先将两个单词按照字母的大小进行排序，然后比较两个单词对应位置上的字母是否相等。

        if (s.length() != t.length()) {
            return false;
        }

        char[] a = s.toCharArray();
        char[] b = t.toCharArray();

        Arrays.sort(a);
        Arrays.sort(b);

        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 【验证回文字符串】
     *
     * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     *
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     *
     * 示例 1:
     *
     * 输入: "A man, a plan, a canal: Panama"
     * 输出: true
     * 示例 2:
     *
     * 输入: "race a car"
     * 输出: false
     */
    public boolean isPalindrome(String s) {

        if (s == null || s.length() == 0) {
            return true;
        }

        s = s.toLowerCase();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9' || s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                stringBuilder.append(s.charAt(i));
            }
        }

        String r = stringBuilder.toString();

        for (int i = 0; i < r.length() / 2; i++) {
            if (r.charAt(i) != r.charAt(r.length() - i - 1)) {
                return false;
            }
        }

        return true;
    }

    /**
     * 【实现 strStr() 函数】
     *
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     *
     * 示例 1:
     *
     * 输入: haystack = "hello", needle = "ll"
     * 输出: 2
     * 示例 2:
     *
     * 输入: haystack = "aaaaa", needle = "bba"
     * 输出: -1
     * 说明:
     *
     * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     *
     * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
     */
    public int strStr(String haystack, String needle) {
        int n=needle.length();//用于记录needle字符串的长度
        if(n==0){//n等于0说明needle是空字符串，返回0
            return 0;
        }
        char cn=needle.charAt(0);//记录needle的第一个字符
        int index=-1;//要返回的索引值，先置为-1
        for(int i=0;i<haystack.length();i++){
            char ch=haystack.charAt(i);
            if(cn==ch){//说明找到了和needle第一个字符相等的字符了
                if(i+n<=haystack.length()){
                    if(needle.equals(haystack.substring(i,i+n))){//说明该子串和needle相等
                        index=i;
                        break;
                    }//end if
                }else{//说明i+n>haystack.length()了，无法截取和needle一样长的子串了
                    break;
                }
            }//end if
        }//end for
        return index;

        // 眼泪掉下来的解法！！！
        // return haystack.indexOf(needle);
    }

    /**
     * 【最长公共前缀】
     *
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     * 示例 1:
     *
     * 输入: ["flower","flow","flight"]
     * 输出: "fl"
     * 示例 2:
     *
     * 输入: ["dog","racecar","car"]
     * 输出: ""
     * 解释: 输入不存在公共前缀。
     * 说明:
     *
     * 所有输入只包含小写字母 a-z 。
     *
     */
    public String longestCommonPrefix(String[] strs) {

        // 思路：首先假设最长前缀result=str[0], 遍历字符串数组，依次与result做比较，
        //      找出其最长前缀，然后更新result，再进行下一次比较。
        if (strs.length == 0) {
            return "";
        }

        String res = strs[0];
        for (String str : strs) {
            while (str.indexOf(res) != 0) {
                res = res.substring(0, res.length() - 1);
                if (res.length() == 0) {
                    return "";
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {

        Solution solution = new Solution();
        int res = solution.strStr("a", "a");
        System.out.println(res);
    }
}
